﻿/** CONSTRAINTSATISFACTIONPROBLEM CLASS
 * Author: Preeti Francis
 * User ID : pxfranci@scotty.cs.wichita.edu
 * WSU ID: S578F746
 * Course: CS771 
 * Sem: S2014
 * 
 * Description of Class : This class returns the constraint satisfaction problem : set of variables [X] i.e., the set of conflicted
 * queens in a randomly shuffled order (using the efficient hashing randomization) and set of conflicts [C]  
 * i.e., conflict values for a particular queen. It makes the necessary checks to understand if a particular queen is in conflict 
 * and the specific number of conflicts for all the rows in a given column.
 * **/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NQueenPuzzle
{
    class ConstraintSatisfactionProblem
    {
        //The chess board dimension
        public int N { get; private set; }
        
        //Constructor
        public ConstraintSatisfactionProblem(int n, int[,] current)
        {
            N = n;

            Current = current;
        }
        
        //Current configuration of the chessboard
        public int[,] Current { get; set; }
        
        //Returns all the conflicted (variables) queens in a randomized shuffled order
        public IList<Queen> GetRandomlyShuffledConflictedQueens()
        {
            var queens = GetRandomlyShuffledQueens();

            var conflictedQueens = from q in queens
                                   where q.IsConflicted == true
                                   select q;

            return conflictedQueens.ToList<Queen>();
            
        }

        //Calculates all the conflicts in a particular row for a selected (variable) queen  
        public IList<TotalConflictsInRow> GetConflictValuesOfRowsForSelectedQueen(int i, int j)
        {
            IList<TotalConflictsInRow> conflictValues = new List<TotalConflictsInRow>();
         
            for (int row = 0; row < N; row++)
            {
                int conflict = GetRowConflicts(row) + GetLowerBackslashConflicts(row, j) + GetLowerForwardSlash(row, j) + GetUpperBackslashConflicts(row, j) + GetUpperForwardSlash(row, j);

                if (row == i)
                {
                    conflict = conflict - 1; // To account for current row conflict so as to not count it twice
                }

                conflictValues.Add(new TotalConflictsInRow{ RowNumber = row, Conflicts = conflict});  
            }

            return conflictValues;
        }

        //Returns a list of all the queens in a randomly shuffled order
        private IList<Queen> GetRandomlyShuffledQueens()
        {
            IList<Queen> queens = new List<Queen>();

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (Current[i,j]==1)
                    {
                        queens.Add(new Queen{
                            ColumnPosition = j,
                            RowPosition = i,
                            IsConflicted = IsQueenInConflict(i,j)
                    });
                    }
                }
            }
            //Induce randomization by ordering by a newly generated hash code
            return queens.OrderBy(q=>q.HashCode).ToList<Queen>();
        }

        //Checks if the queen is in conflict  
        private bool IsQueenInConflict(int queenRowPosition, int queenColumnPosition)
        {
            //check in row 
            int conflict_row = GetRowConflicts(queenRowPosition) - 1;

            if (conflict_row > 0)
            {
                return true;
            }
            
            //check in column : redundant since we are getting a single queen per column
            int conflict_column = GetColumnConflicts(queenColumnPosition) - 1;

            if (conflict_column > 0)
            {
                return true;
            }
            
            //Backslash i.e left diagonal
            int conflict_BackSlash = (GetLowerBackslashConflicts(queenRowPosition, queenColumnPosition) + GetUpperBackslashConflicts(queenRowPosition, queenColumnPosition));

            if (conflict_BackSlash>0)
            {
                return true;
            }

            //Forwardslash i.e right diagonal
            int conflict_ForwardSlash = (GetLowerForwardSlash(queenRowPosition, queenColumnPosition) + GetUpperForwardSlash(queenRowPosition, queenColumnPosition));

            if (conflict_ForwardSlash>0)
            {
                return true;
            }

            return false;
        }
        
        //Calculate conflicts in upper left diagonals
        private int GetUpperBackslashConflicts(int i, int j)
        {
            int conflict_upperBackslash = 0;
            int row = i - 1;
            int col = j - 1;

            while (row >= 0 && col >= 0)
            {

                conflict_upperBackslash = conflict_upperBackslash + Current[row, col];

                row = row - 1;
                col = col - 1;
            }

            return conflict_upperBackslash;
        }

        //Calculate conflicts in lower left diagonals
        private int GetLowerBackslashConflicts(int i, int j)
        {
            int conflict_lowerBackslash = 0;
            int row = i + 1;
            int col = j + 1;

            while (row < N && col < N)
            {
                conflict_lowerBackslash = conflict_lowerBackslash + Current[row, col];

                row = row + 1;
                col = col + 1;
            }

            return conflict_lowerBackslash;
        }

        //Calculate conflicts in lower right diagonals
        private int GetLowerForwardSlash(int i, int j)
        {
            int conflict_lowerForwardslash = 0;
            int row = i + 1;
            int col = j - 1;

            while (row < N && col >= 0)
            {
                conflict_lowerForwardslash = conflict_lowerForwardslash + Current[row, col];

                row = row + 1;
                col = col - 1;
            }

            return conflict_lowerForwardslash;
        }

        //Calculate conflicts on upper right diagonals
        private int GetUpperForwardSlash(int i, int j)
        {
            int conflict_upperForwardslash = 0;
            int row = i - 1;
            int col = j + 1;

            while (row >= 0 && col < N)
            {
                conflict_upperForwardslash = conflict_upperForwardslash + Current[row, col];

                row = row - 1;
                col = col + 1;
            }

            return conflict_upperForwardslash;
        }

        //Get conflicts in column : redundant since we are getting a single queen per column
        private int GetColumnConflicts(int j)
        {
            int conflict_column = 0;

            for (int row = 0; row < N; row++)
            {
                conflict_column = conflict_column + Current[row, j];
            }

            return conflict_column;
        }

        //Calculate conflicts in a row
        private int GetRowConflicts(int i)
        {
            int conflict_row = 0;

            for (int col = 0; col < N; col++)
            {
                conflict_row = conflict_row + Current[i, col];
            }
            
            return conflict_row;
        }
    }
}
